//
// Created by user on 2022/2/14.
//
#include <iostream>
#include <vector>

using namespace std;

//归并排序

void mergeSort(vector<int>& nums, int lo, int hi, vector<int> &tmp);
void merge(vector<int>& nums, int lo, int mid, int hi, vector<int> &tmp);

vector<int> sortArray(vector<int>& nums) {
    vector<int> tmp(nums.size(), 0);
    mergeSort(nums, 0, nums.size()-1, tmp);
    return nums;

}

void mergeSort(vector<int>& nums, int lo, int hi, vector<int> &tmp){
    if(lo>=hi){return;}
    int mid = lo+(hi-lo)/2;
    mergeSort(nums, lo, mid, tmp);
    mergeSort(nums, mid+1, hi, tmp);
    merge(nums, lo, mid, hi, tmp);

}

void merge(vector<int>& nums, int lo, int mid, int hi, vector<int> &tmp){
    for (int i = lo; i <= hi; ++i) {
        tmp[i] = nums[i];
    }
    int i = lo;
    int j = mid+1;
    for (int k = lo; k <= hi; ++k) {
        if(i==mid+1){
            nums[k] = tmp[j++];
        } else if(j==hi+1){
            nums[k] = tmp[i++];
        }else if(tmp[i]<=tmp[j]){
            nums[k]=tmp[i++];
        } else{
            nums[k]=tmp[j++];
        }
    }
}

//快排排序
int partition(vector<int>& nums, int lo, int hi);
void quickSort(vector<int>& nums, int lo, int hi);
vector<int> sortArray1(vector<int>& nums) {
    quickSort(nums, 0, nums.size()-1);
    return nums;

}

void quickSort(vector<int>& nums, int lo, int hi){
    if (lo >= hi) return;
    int index = partition(nums, lo, hi);
    quickSort(nums, lo, index-1);
    quickSort(nums, index+1, hi);
}

int partition(vector<int>& nums, int lo, int hi){
    int i = rand()%(hi-lo+1)+lo;//随机数的产生
    //交换
    swap(nums[i], nums[hi]);
    //基数
    int pivot = nums[hi];
    int less = lo;
    int great = lo;
    for (; great <= hi-1; great++) {
        if(nums[great]<pivot){
            swap(nums[less], nums[great]);
            less++;
        }
    }
    swap(nums[less], nums[hi]);
    return less;
}

//三路快排 对于大量重复值有利
void threeQuickSort(vector<int>& nums, int lo, int hi);
vector<int> sortArray2(vector<int>& nums) {

    threeQuickSort(nums, 0, nums.size()-1);
    return nums;
}

void threeQuickSort(vector<int>& nums, int lo, int hi){
    if(lo>=hi){return;}

    int i = rand()%(hi-lo+1)+lo;
    swap(nums[i], nums[hi]);
    int pivot = nums[hi];

    int less = lo;
    int great = hi;

    i = lo;
    while (i<=great){
        if(nums[i]<pivot){
            swap(nums[i], nums[less]);
            less++;
            i++;
        }else if(nums[i]>pivot){
            swap(nums[i], nums[great]);
            great--;
        } else{
            i++;
        }
    }
    threeQuickSort(nums, lo, less-1);
    threeQuickSort(nums, great+1, hi);
}


